/*
 * @lc app=leetcode.cn id=442 lang=cpp
 *
 * [442] 数组中重复的数据
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <map>

using namespace std;
// @lc code=start
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        // int n = nums.size();
        // vector<int> ret;
        // //遍历数组，让每个出现过的数所在的位置加n
        // for(int i = 0;i < n;i++){
        //     int x = (nums[i] - 1) % n;
        //     nums[x] += n;
        // }
        // for(int i = 0;i < n;i++){
        //     int x = nums[i];
        //     if(nums[i] > 2 * n) {
        //         ret.push_back(i + 1);
        //     }
        // }
        // return ret;

        unordered_set<int> hash_set;
        vector<int> ret;
        for(int i = 0;i < nums.size();i++) {
            if(hash_set.count(nums[i]) == 1) {
                ret.push_back(nums[i]);
            }
            hash_set.insert(nums[i]);
        }
        return ret;

    }
};
// @lc code=end

/**
 * @brief 空间复杂度为O(n)
        int n = nums.size();
        vector<int> arr(n+1,0);
        vector<int> ret;
        for(int i = 0;i < n;i++){
            if(arr[nums[i]] == 1) {
                ret.push_back(nums[i]);
            }
            arr[nums[i]] = 1;
        }
        return ret;
 * 
 */
